package com.leetcode.LeetCode精选TOP面试题;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 覃国强
 * @date 2022-07-08 14:23
 */
public class 题库_0208_实现_Trie_前缀树 {

  static
  class Trie {

    private Node root;

    public Trie() {
      this.root = new Node();
    }

    public void insert(String word) {
      Node node = root;
      for (int i = 0; i < word.length(); ++i) {
        char letter = word.charAt(i);
        node.edges.putIfAbsent(letter, new Node());
        node = node.edges.get(letter);
      }
      node.end = true;
    }

    public boolean search(String word) {
      Node node = searchPrefix(word);
      return node != null && node.end;
    }

    public boolean startsWith(String prefix) {
      return searchPrefix(prefix) != null;
    }

    private Node searchPrefix(String prefix) {
      Node node = root;
      for (int i = 0; i < prefix.length(); ++i) {
        char letter = prefix.charAt(i);
        if (!node.edges.containsKey(letter)) {
          return null;
        }
        node = node.edges.get(letter);
      }
      return node;
    }

    static class Node {

      boolean end;

      Map<Character, Node> edges;

      Node() {
        this.edges = new HashMap<>();
        this.end = false;
      }
    }
  }

}
